package leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class LeetcodeMain84{
    
    class node{
        int num;
        int count;
        public node(int num, int count) {
            this.num = num;
            this.count = count;
        }
    }
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map=new HashMap<>();
        for (int num:nums) {
            map.put(num,map.getOrDefault(num,0)+1);
        }
        PriorityQueue<node> queue=new PriorityQueue<>((o1, o2) -> o1.count-o2.count);
        for (Map.Entry<Integer,Integer> set:map.entrySet()) {
            if (queue.size()<k){
                queue.add(new node(set.getKey(),set.getValue()));
            }
            else {
                if (queue.peek().count<set.getValue()){
                    queue.poll();
                    queue.add(new node(set.getKey(),set.getValue()));
                }
            }
        }

        int[] arr=new int[k];
        for (int i = 0; i < k; i++) {
            arr[i]=queue.poll().num;
        }
        return arr;
    }
    public int[] countBits(int n) {
        int[] arr=new int[n+1];
        for (int i = 1; i <= n; i++) {
            arr[i]=numOne(i);
        }
        return arr;
    }
    public int numOne(int num){
        int count=0;
        while (num!=0){
            count++;
            num=num&(num-1);
        }
        return count;
    }
}